Trójkąty jednobarwne

Limit pamięci: 32 MB

W przestrzeni rozmieszczono punktów w taki sposób, że żadne trzy z nich nie są współliniowe. Następnie każdą parę tych punktów połączono odcinkiem i każdy odcinek pokolorowano na czarno albo na czerwono. Trójkątem jednobarwnym nazwiemy każdy trójkąt mający wszystkie trzy boki tego samego koloru. Mamy daną listę wszystkich czerwonych odcinków. Chcemy znaleźć liczbę wszystkich trójkątów jednobarwnych.

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia: liczbę punktów, liczbę odcinków czerwonych oraz ich listę,
• znajduje liczbę trójkątów jednobarwnych,
• zapisuje wynik na standardowe wyjście.

Wejście

W pierwszym wierszu standardowego wejścia jest zapisana jedna liczba całkowita spełniająca nierówności . Jest to liczba punktów. W drugim wierszu jest zapisana jedna liczba całkowita spełniająca nierówności . Jest to liczba odcinków czerwonych.

W każdym z kolejnych wierszy są zapisane dwie liczby całkowite oraz , oddzielone pojedynczym odstępem i spełniające nierówność: . Są to numery wierzchołków będących końcami kolejnego odcinka czerwonego.

Wyjście

W pierwszym i jedynym wierszu standardowego wyjścia należy zapisać jedną liczbę całkowitą — liczbę trójkątów jednobarwnych.

Przykład

Dla danych wejściowych:

6
9
1 2
2 3
2 5
1 4
1 6
3 4
4 5
5 6
3 6

poprawną odpowiedzią jest:

2

Autor zadania: Wojciech Guzicki.